package com.huangyi;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    //K 个一组翻转链表
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    static class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            if (head == null || k <= 1) return head; // 边界：k=1 或空链表无需处理

            // 1) 统计长度，确定完整分组数
            int n = 0;
            ListNode curr = head;
            while (curr != null) {
                n++;
                curr = curr.next;
            }
            int count = n / k;
            if (count == 0) return head; // 不足一组，直接返回

            // 2) 准备哑节点与"钩子"指针
            ListNode dummy = new ListNode(0);
            dummy.next = head;               // 哑节点用于返回结果
            ListNode dummyPrev = dummy;      // 左钩子：已处理前缀的尾
            ListNode start = head;           // 右钩子：当前分组原头（反转后成为新尾）

            // 3) 逐组处理
            for (int i = 0; i < count; i++) {
                // 3.1 段内反转 k 次
                ListNode prev = null;
                curr = start; // 从本组原头开始反转
                for (int j = 0; j < k; j++) {
                    ListNode next = curr.next;
                    curr.next = prev;
                    prev = curr;
                    curr = next; // 正确推进到未反转部分
                }
                // 此时：prev=本组新头，start=本组新尾（原头），curr=下一段起点

                // 3.2 段间连边（两条都要！）
                dummyPrev.next = prev; // 左边：上一段尾 -> 本组新头
                start.next = curr;     // 右边：本组新尾(原start) -> 下一段起点

                // 3.3 钩子前移，开始下一组
                dummyPrev = start; // 新尾成为已处理前缀的尾
                start = curr;      // 下一组原头
            }

            // 4) 返回结果
            return dummy.next;
        }
    }

    //两数之和
    static class Solution2 {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer,Integer> hash = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
                int need = target - nums[i];
                int j = hash.getOrDefault(need, -1); // -1 不与合法索引冲突
                if (j != -1) return new int[]{j, i};
                hash.put(nums[i], i);
            }
            return new int[0];
        }
    }
}
